package algo.tree;


import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTreeMap<T extends Comparable<? super T>, V>{

    protected int N;
    protected RBTreeNode<T, V> head;
    protected RBTreeNode<T, V> root;

    protected static final boolean COLOR_BLACK = true;
    protected static final boolean COLOR_RED = false;
    public RedBlackTreeMap() {
        N = 0;
        head = new RBTreeNode<>();
        root = null;
    }

    public void printPreTraverse() {
        System.out.println("\nPreOrder Traverse:");
        RBTreeNode<T, V> node = root;
        printPreTraverseRecurrence(node);
        System.out.println();
    }
    protected void printPreTraverseRecurrence(RBTreeNode<T, V> node) {
        if (node == null) return;

        printPreTraverseRecurrence(node.left);
        System.out.print(node.key + " ");
        printPreTraverseRecurrence(node.right);
    }
    public void printMidTraverse() {
        System.out.println("\nMidOrder Traverse:");
        RBTreeNode<T, V> node = root;
        printMidTraverseRecurrence(node);
        System.out.println();
    }
    protected void printMidTraverseRecurrence(RBTreeNode<T, V> node) {
        if (node == null) return;

        System.out.print(node.key + " ");
        printMidTraverseRecurrence(node.left);
        printMidTraverseRecurrence(node.right);
    }
    public void printPostTraverse() {
        System.out.println("\nPostOrder Traverse:");
        RBTreeNode<T, V> node = root;
        printPostTraverseRecurrence(node);
        System.out.println();
    }
    protected void printPostTraverseRecurrence(RBTreeNode<T, V> node) {
        if (node == null) return;

        printPostTraverseRecurrence(node.left);
        printPostTraverseRecurrence(node.right);
        System.out.print(node.key + " ");
    }
    public void printLevelTraverse() {
        System.out.println("\nLevel Traverse:");
        if (root == null) return;

        RBTreeNode<T, V> node = root;
        Queue<RBTreeNode<T, V>> queue = new LinkedList<>();
        queue.add(node);

        while (queue.size() > 0) {
            int size = queue.size();

            while (size-- > 0) {
                node = queue.poll();
                if (node == root) System.out.print("<"+node.key + ","+node.value+"> ");
                else System.out.print("<"+node.parent.key + ","+node.parent.value+">"
                        +"."+(node==node.parent.left?"left=":"right=")
                        +"<"+node.key + ","+node.value+">" +"\t");
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            System.out.println();
        }
    }




    public V search(T key) {
        if (lastSearch != null && equalTo(lastSearch.key, key)) return lastSearch.value;

        RBTreeNode<T, V> node = root;
        while (node != null) {
            int cmp = compare(key, root.key);

            if (cmp < 0)        node = node.left;
            else if (cmp > 0)   node = node.right;
            else                {
                lastSearch = node;
                return  node.value;
            }
        }
        return null;
    }
    public V searchOfDefault(T key, V defVal) {
        if (lastSearch != null && equalTo(lastSearch.key, key)) return lastSearch.value;

        RBTreeNode<T, V> node = root;
        while (node != null) {
            int cmp = compare(key, root.key);

            if (cmp < 0)        node = node.left;
            else if (cmp > 0)   node = node.right;
            else                {
                lastSearch = node;
                return  node.value;
            }
        }
        return defVal;
    }
    protected RBTreeNode<T, V> lastSearch = null;
    public boolean containsKey(T key) {
        if (lastSearch != null && equalTo(lastSearch.key, key)) {
            return true;
        }
        RBTreeNode<T, V> node = root;
        while (node != null) {
            int cmp = compare(key, root.key);

            if (cmp < 0)        node = node.left;
            else if (cmp > 0)   node = node.right;
            else {
                lastSearch = node;
                return true;
            }
        }
        return false;
    }
    /*
        public boolean insert(T key) {
            // 1. 按照二叉搜索树的规则插入新节点
            // 空树
            if (root == null) {
                root = new RBTreeNode<>(head, key, COLOR_BLACK);
                head.parent = root;
                ++N;
            } else {
                // 非空
                // 按照二叉搜索树的特性找待插入节点在树中的位置
                RBTreeNode<T> node = root;
                RBTreeNode<T> parent;
                int cmp;

                do {
                    parent = node;
                    cmp = compare(key, node.val);

                    if (cmp < 0)        node = node.left;
                    else if (cmp > 0)   node = node.right;
                    else                return false;
                } while (node != null);

                // 插入新节点
                node = new RBTreeNode<>(parent, key);
                if (cmp < 0)    parent.left = node;
                else            parent.right = node;

                ++N;
                // 2. 检测新节点插入之后是否违反性质三：即是否存在红色节点连在一起的情况
                //    因为新插入节点cur的颜色是红色的，如果cur双亲parent节点的颜色也是红色的
                //    则违反了性质三
                while (isRed(parent)) {
                    // 违反了性质三
                    RBTreeNode<T> grandParent = parent.parent;

                    // 此处grandFather一定不为空
                    // 因为：parent是红色的，则parent一定不是根节点，parent的双亲一定是存在的
                    if (parent == grandParent.left) {
                        // 三种情况
                        RBTreeNode<T> uncle = grandParent.right;
                        if (uncle != null && isRed(uncle)) {
                            // 情况一：叔叔节点存在且为红
                            parent.color = COLOR_BLACK;
                            uncle.color = COLOR_BLACK;
                            grandParent.color = COLOR_RED;
                            node = grandParent;
                            parent = node.parent;
                        } else {
                            // 叔叔节点为空 || 叔叔节点存在且为黑--->即情况二 或者 情况三
                            // 情况三
                            if (node == parent.right) {
                                // 先对parent进行左单旋，然后将parent和cur交换---->变成情况二
                                rotateLeft(parent);
                                swap(parent, node);
                            }

                            // 情况二：
                            // 将祖父和双亲节点的颜色交换，然后再对祖父树进行右单旋
                            grandParent.color = COLOR_RED;
                            parent.color = COLOR_BLACK;
                            rotateRight(grandParent);
                        }
                    } else {
                        // 三种情况
                        RBTreeNode<T> uncle = grandParent.left;
                        if (uncle != null && isRed(uncle)) {
                            // 情况一：叔叔节点存在且为红
                            parent.color = COLOR_BLACK;
                            uncle.color = COLOR_BLACK;
                            grandParent.color = COLOR_RED;
                            node = grandParent;
                            parent = node.parent;
                        } else {
                            // 叔叔节点为空 || 叔叔节点存在且为黑--->即情况二 或者 情况三
                            // 情况三
                            if (node == parent.left) {
                                // 先对parent进行右单旋，然后将parent和node交换---->变成情况二
                                rotateRight(parent);
                                swap(parent, node);
                            }

                            // 情况二：
                            // 将祖父和双亲节点的颜色交换，然后再对祖父树进行左单旋
                            grandParent.color = COLOR_RED;
                            parent.color = COLOR_BLACK;
                            rotateLeft(grandParent);
                        }
                    }
                }
            }

            head.left = getMostLeft();
            head.right = getMostRight();
            root.color = COLOR_BLACK;
            return true;
        }
    */
    public boolean insert(T key, V value) {
        // 1. 按照二叉搜索树的规则插入新节点
        // 空树
        if (root == null) {
            root = new RBTreeNode<>(head, key, value, COLOR_BLACK);
            head.parent = root;
            ++N;
        } else {
            // 非空
            // 按照二叉搜索树的特性找待插入节点在树中的位置
            RBTreeNode<T, V> node = root;
            RBTreeNode<T, V> parent;
            int cmp;

            do {
                parent = node;
                cmp = compare(key, node.key);

                if (cmp < 0)        node = node.left;
                else if (cmp > 0)   node = node.right;
                else                return false;
            } while (node != null);

            // 插入新节点
            node = new RBTreeNode<>(parent, key, value);
            if (cmp < 0)    parent.left = node;
            else            parent.right = node;

            ++N;
            lastSearch = node;
            // 2. 检测新节点插入之后是否违反性质三：即是否存在红色节点连在一起的情况
            //    因为新插入节点cur的颜色是红色的，如果cur双亲parent节点的颜色也是红色的
            //    则违反了性质三
            if (isRed(parent))
                fixAfterInsertion2(node);
        }

        head.left = getMostLeft();
        head.right = getMostRight();
        root.color = COLOR_BLACK;
        return true;
    }

    protected void fixAfterInsertion2(RBTreeNode<T, V> node) {
        do {
            RBTreeNode<T, V> uncle;
            if (node.parent == node.parent.parent.left) {
                uncle = node.parent.parent.right;
                if (isRed(uncle)) {
                    paintRed(node.parent.parent);
                    paintBlack(node.parent);
                    paintBlack(uncle);
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }

                    paintBlack(node.parent);
                    paintRed(node.parent.parent);
                    rotateRight(node.parent.parent);
                }
            } else {
                uncle = node.parent.parent.left;
                if (isRed(uncle)) {
                    paintRed(node.parent.parent);
                    paintBlack(node.parent);
                    paintBlack(uncle);
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rotateRight(node);
                    }

                    paintBlack(node.parent);
                    paintRed(node.parent.parent);
                    rotateLeft(node.parent.parent);
                }
            }

        } while (isRed(node.parent));
    }
    protected void fixAfterInsertion(RBTreeNode<T, V> node) {
        while (isRed(node.parent)) {
            RBTreeNode<T, V> uncle;
            if (parentOf(node) == parentOf(parentOf(node)).left) {
                uncle = parentOf(parentOf(node)).right;
                if (isRed(uncle)) {
                    parentOf(node).color = COLOR_BLACK;
                    uncle.color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    node = parentOf(parentOf(node));
                } else {
                    if (node == parentOf(node).right) {
                        node = parentOf(node);
                        rotateLeft(node);
                    }

                    parentOf(node).color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    rotateRight(parentOf(parentOf(node)));
                }
            } else {
                uncle = parentOf(node).left;
                if (isRed(uncle)) {
                    parentOf(node).color = COLOR_BLACK;
                    uncle.color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    node = parentOf(parentOf(node));
                } else {
                    if (node == parentOf(node).left) {
                        node = parentOf(node);
                        rotateRight(node);
                    }

                    parentOf(node).color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    rotateLeft(parentOf(parentOf(node)));
                }
            }
        }
    }


    protected RBTreeNode<T, V> parentOf(RBTreeNode<T, V> node) {
        return node == null ? null : node.parent;
    }

    protected void rotateLeft(RBTreeNode<T, V> node) {
        RBTreeNode<T, V> rightChild = node.right;
        node.right = rightChild.left;
        if (rightChild.left != null)
            rightChild.left.parent = node;

        rightChild.parent = node.parent;
        if (node.parent == head) {
            head.parent = rightChild;
            root = rightChild;
        } else if (node.parent.left == node) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }
        rightChild.left = node;
        node.parent = rightChild;
    }

    protected void rotateRight(RBTreeNode<T, V> node) {
        RBTreeNode<T, V> leftChild = node.left;
        node.left = leftChild.right;
        if (leftChild.right != null)
            leftChild.right.parent = node;

        leftChild.parent = node.parent;
        if (node.parent == head) {
            head.parent = leftChild;
            root = leftChild;
        } else if (node.parent.left == node) {
            node.parent.left = leftChild;
        } else {
            node.parent.right = leftChild;
        }
        leftChild.right = node;
        node.parent = leftChild;
    }

/*
    protected void swap(RBTreeNode<T> a, RBTreeNode<T> b) {
    // 颜色也需要交换吗？
        T tmp = a.val;
        a.val = b.val;
        b.val = tmp;
    }
*/

    protected RBTreeNode<T, V> getMostLeft() {
        RBTreeNode<T, V> node = root;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    protected RBTreeNode<T, V> getMostRight() {
        RBTreeNode<T, V> node = root;
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    class RBTreeNode<T, V> {
        public boolean color;
        public T key;
        public V value;
        public RBTreeNode<T, V> left;
        public RBTreeNode<T, V> right;
        public RBTreeNode<T, V> parent;

        RBTreeNode() {
            color = COLOR_BLACK;
        }
        RBTreeNode(RBTreeNode parent, T key, V value) {
            this.key = key;
            this.value = value;
            this.parent = parent;
            color = COLOR_RED;
        }
        RBTreeNode(RBTreeNode parent, T key, V value, boolean color) {
            this.key = key;
            this.value = value;
            this.parent = parent;
            this.color = color;
        }
    }
    protected boolean less(T a, T b) {
        return a.compareTo(b) < 0;
    }
    protected boolean greater(T a, T b) {
        return a.compareTo(b) > 0;
    }

    protected int compare(T a, T b) {
        return a.compareTo(b);
    }
    protected boolean equalTo(T a, T b) {
        return a.compareTo(b) == 0;
    }
    protected boolean isBlack(RBTreeNode<T, V> node) {
        return node == null || node.color;
    }

    protected void paintBlack(RBTreeNode<T, V> node) {
        if (node != null) node.color = COLOR_BLACK;
    }
    protected void paintRed(RBTreeNode<T, V> node) {
        if (node != null) node.color = COLOR_RED;
    }


    protected boolean isRed(RBTreeNode<T, V> node) {
        return node != null && !node.color;
    }
}
